package com.justnow.offer;


import java.util.HashMap;
import java.util.LinkedList;

/**
 * @author justnow
 * Created on 2020-09-30
 * Description
 */
public class LRUCache {
    private HashMap<Integer, Node> map;
    private LinkedList<Node> cache;
    private int size;

    public LRUCache(int size) {
        this.size = size;
        this.map = new HashMap<>();
        this.cache = new LinkedList<>();
    }

    public int get(int index) {
        if (!map.containsKey(index)) {
            return -1;
        }
        Node node = map.get(index);
        // 利用put方法把该数据提前
        put(index, node.val);
        return node.val;
    }

    public void put(int index, int val) {
        // 先把节点做出来
        Node node = new Node(index, val);
        if (map.containsKey(index)) {
            //Linkedlist来move时是根据equals的一次每个节点是否相同的，所以不能用自己的创建node来作为remove的参数
            //而应该通过map的key来获取这个节点
            cache.remove(map.get(index));
            cache.addFirst(node);
            //这里需要更新，该节点，因为这次是自己创建的对象。
            map.put(index, node);
        } else {
            if (size == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.index);
            }
            // 直接添加到头部
            cache.addFirst(node);
            // 每次，添加元素的同时需要将该节点放入到map中
            map.put(index, node);
        }
    }

/*
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));     // 返回  1
        cache.put(3, 3);    // 该操作会使得关键字 2 作废
        System.out.println(cache.get(2));     // 返回 -1 (未找到)
        cache.put(4, 4);    // 该操作会使得关键字 1 作废
        System.out.println(cache.get(1)); // 返回 -1 (未找到)
        System.out.println(cache.get(3));       // 返回  3
        System.out.println(cache.get(4));       // 返回  4
    }
*/
}

class Node {
    int index, val;

    public Node(int index, int val) {
        this.index = index;
        this.val = val;
    }
}

